#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
    public:
	int networkDelayTime(vector<vector<int>> &times, int n, int k)
	{
                vector<vector<vector<int>>> gh(n + 1);
                for(auto e : times){
                        gh[e[0]].push_back({e[1], e[2]});
                }

                vector<int> vis(n + 1, 0), dis(n + 1, INT32_MAX);
                auto cmp = [](auto a, auto b){ return a.second > b.second; };
                priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

                pq.push({k, 0});
                dis[k] = 0;
                int ans = 0, cnt = 0;
                while(!pq.empty()){
                        auto e = pq.top();
                        pq.pop();
                        int u = e.first, w = e.second;
                        if(vis[u]){
                                continue;
                        }
                        vis[u] = 1;
                        ans = max(ans, dis[u]);
                        cnt++;
                        for(auto e : gh[u]){
                                int v = e[0];
                                if(!vis[v] && e[1] + w < dis[v]){
                                        dis[v] = e[1] + w;
                                        pq.push({v, dis[v]});
                                }
                        }
                }
                return cnt == n ? ans : -1;
	}
};

int main()
{       
	vector<vector<int>> times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
	int n = 4, k = 2;
	cout << Solution().networkDelayTime(times, n, k) << endl;
	return 0;
}
